\subsection{Method II} 
\label{method2}
The main steps of the algorithm is briefly summarized below. Each of the individual steps will be given a more thorough explanation below.

\begin{enumerate} 
\item Split the partial graph into smaller, overlapping subgraphs. This is done by using some background information from the graph database so as to limit the number of possible splittings.
\item For each of these subgraphs of the partial graph, determine the probability of every possible edit operation.

\item Combine the results of the estimates of the edit operations for each subgraph into a final solution for the whole partial graph.
\end{enumerate}

These three steps are summarized in figure \ref{fig:sysoverviewb}.
Besides these, in the pre-processing step, we extract frequent subgraphs from the graph database using the $\mathrm{gSpan}$ Algorithm \cite{gSpan}.
This will provide us with a frequent subgraph database $\mathcal{S}$ which is used in the first step of the prediction. See figure \ref{fig:sysoverviewa}.\\
\indent \emph{Step 1:}
The aim of this step is to divide the partial input graph $G_p$ into a set of overlapping connected subgraphs $C$ where $\forall x \in C, \exists y \in C, x \cap y \neq \emptyset$.
The procedure for computing $C$ is given in Algorithm~\ref{alg:graphpartalg}. The selection of subgraphs plays an important role in prediction quality. We pick the elements of $C$ as much as possible from the frequent graph set $\mathcal{S}$.
The rationale behind this is that since indoor topologies consists of multiple functional smaller parts, the algorithm should try to identify those and later expand them as viable predictions. 
First we determine which of the frequent subgraphs from $\mathcal{S}$ that are present in the current partial graphs, and extract the largest possible such frequent subgraphs set and call it $P$. 

In short, Algorithm~\ref{alg:graphpartalg} iteratively checks for the elements of $S$ which are included in $G_p$ (the set $P$) and which shares at least one vertex with the list of subgraphs found so far, $C$, so as to disregard disconnected subgraphs. Another reason is that computing the list of all possible connected subgraphs of $G_p$ becomes intractable even for small sized graphs. Therefore we utilize the frequent subgraphs of the graph database to bootstrap this computation and cut down the search space.\\ 
\indent \emph{Step 2:}
In this step, we aim to calculate the probability of all possible edit operations for each subgraph of $G_p$. 
Let $\mathcal{D}_{C_i}$ be the projected database of any subgraph $C_i$ of $G_p$, that is, the set of all those graphs which are supersets of $C_i$.
Let $x$ be some graph which is one edit operation away from $C_i$, that is $x \in B(C_i, 1)$. We then define
$\phi(x, C_i) =  | \{G' \in \mathcal{D}_{C_i} | x \subseteq G' \} |$. That is $\phi(x, C_i)$ gives the number of times we've observed a specific edit operation upon $C_i$ among all the graphs.
The most likely edit operation to perform given that we've observed the subgraph $C_i$ is then given by $\underset{x \in B(C_i, 1)}{\operatorname{arg\,max}} \phi(x, C_i)$. This procedure is given in detail in algorithm~\ref{alg:optimalgraphedit}.\\
\indent \emph{Step 3:}
Given that we have calculated the most likely edit operation for each of the subgraphs $C_1, ..., C_n$, we have for each of these an optimal edit operation leading to new graphs $C_1', ..., C_n'$
respectively. We must select one of these, and for any selection $C_j'$ made, the resulting prediction will be $G_p' = \bigcup_{i \in [1,n] \setminus \{j\}} C_i \cup C_j'$.
We simply select the edit operation which has the highest support from the graph database. That is, $\underset{C_i, i \in [1,n]}{\operatorname{arg\,max}} \phi(C_i, C_i')$.\\\\
Given the function $\phi : \mathcal{G} \times \mathcal{G} \to \mathbb{N}$, it is possible to arrive at an estimate of the discrete probability distribution of the different edit operations upon $G_p$.
The distribution is calculated in a frequentist manner and is given by: 

\begin{equation}
P(G_p'=x)=\dfrac{\phi(x, C_j)}{\sum_{y \in B(C_j, 1)} \phi(y, C_j)}, x \in B(C_j, 1)
\end{equation} 

$C_j$ here refers to the selected subgraph and is chosen as detailed above.

Figure \ref{fig:PartGP} shows the initial partial graph which is the input to the prediction algorithm. In this example the input graph is divided into three subgraphs. The output of the first step of the algorithm is shown in black in figure \ref{fig:Part1}, \ref{fig:Part2} and \ref{fig:Part3}. In the second step, the predicted edit operation with the highest support for each subgraph $C_i$ is shown in green. Finally, in the third step, the edit operation with the highest probability is selected.
 
This splitting of the input graph agrees with the claim that indoor topologies consist of smaller functional parts. Figure {\ref{fig:Part1} shows that vertices that are not commonly occuring are grouped together, forming a ``maintenance'' functional group. Figure \ref{fig:Part3} shows a very common structure, with a corridor as a root node.
Finally, in figure \ref{fig:Part2}, we can see that the algorithm has identified a lobby group. This is also quite common, that the lobby acts as a root node similar to a corridor vertex connected in a tree-like structure.
 
\begin{figure*}
  \centering
  \subfloat[The input partial graph.]{\label{fig:PartGP}\includegraphics[scale=0.4]{figures/PartGP}} \\            
  \hspace{2mm}
  \subfloat[First subgraph]{\label{fig:Part1}\includegraphics[scale=0.4]{figures/PartC1}}
  \hspace{2mm}
  \subfloat[Second subgraph]{\label{fig:Part2}\includegraphics[scale=0.4]{figures/PartC2}}
  \subfloat[Third subgraph]{\label{fig:Part3}\includegraphics[scale=0.4]{figures/PartC3}}
  \hspace{2mm}
  \caption{The overlapping subgraphs of a partial graph.}
  \label{fig:Partition}
\end{figure*}

%-----------------------------------------------
\begin{algorithm}
\caption{Graph splitting}
\label{alg:graphpartalg}

Input:
\begin{itemize}

\item $G_p$, the current partial graph

\end{itemize}

Output:
\begin{itemize}
\item $C=\{C_1, ..., C_m\}$, the overlapping subgraphs of the
partial graph
\end{itemize}


\begin{algorithmic}[1]
%\IF {$i\geq maxval$} 
\STATE $P \gets \emptyset$
\FOR{$ s \in \mathcal{S} $}
\IF{$s \subseteq G_p  \wedge (\neg\exists s' \in \mathcal{S}, s \subseteq s', s' \subseteq G_p) \ $} 
\STATE $P \gets P \cup \{ s \}$ 
\ENDIF
\ENDFOR

\COMMENT {$P$ now contains those frequent subgraphs which are contained in the partial graph $G_p$. They are also the largest possible frequent subgraphs. }
\STATE $\mathrm{sort(P)}$ by graph size, descending.
\STATE $C \gets \{ \mathrm{FindCommonFreqSubgraph}(P, G_p, \emptyset) \}$

\WHILE{$|G_p| \neq |\bigcup_{i=1}^n C_i|$}

\STATE $Found \gets 0$

% Do the partitioning
\FORALL{$ c \in C \wedge Found = 0 $}

\STATE $c' \gets \mathrm{FindCommonFreqSubgraph}(P, c, C) $
\IF{$c' \neq \emptyset$}

\STATE $C \gets C \cup c'$
\STATE $Found \gets 1$
\STATE break
%\RETURN $C$
\ENDIF

\ENDFOR

\IF{ $Found = 0$ }
\STATE $D_g \gets G_p \setminus \bigcup_{i=1}^n C_i$
\STATE Add the following vertex set to $D_g$: $\bigcup_{v \in V(D_g)} N(v, G_p) \setminus D_g$
\STATE Add the edges (from the edge set of $G_p$) which correspond to the vertex additions above.
\STATE $C \gets C \cup \mathrm{GetComponents}(D_g)$
\RETURN $C$
\ENDIF

\ENDWHILE

\RETURN $C$

\end{algorithmic}
\end{algorithm}§
%-----------------------------------------------


%------------------------------------------------------------------------------------

\begin{algorithm}
\caption{FindCommonFreqSubgraph}
\label{findcommonfsubgraph}

This function will attempt to find another frequent subgraph from the set $P$ that has some vertex in common
with some graph $C_i$ (the already established subgraphs of $G_p$).

Input:
\begin{itemize}

\item $P$, the sorted sequence of frequent subgraphs that are present in the partial graph
\item $G$, a graph which the result should have some vertex
in common with, this is always some $C_i$ except for the
initial execution.
\item $C=\{C_1, ..., C_n\}$, the thus far added overlapping subgraphs of the partial graph 

\end{itemize}

Output:
\begin{itemize}
\item $p$, the largest frequent subgraph present in the partial
graph that has atleast one vertex in common with $G$ (if
found). $p$ is also removed from the set $P$. If no such $p$
could be found, it returns the empty graph $\emptyset$.
\end{itemize}

\begin{algorithmic}[1]

\FORALL{$ p \in P $}
\IF{$\mathrm{HasVertexInCommon}(G, p) \wedge p \not\subseteq \bigcup_{i=1}^n C_i $}
 \STATE $P \gets P \setminus \{ p \}$ 
\RETURN p
\ENDIF
\ENDFOR

\RETURN $\emptyset$

\end{algorithmic}
\end{algorithm}

%------------------------------------------------------------------------------------




%-----------------------------------------------
\begin{algorithm}
\caption{Find most likely graph edit operation}
\label{alg:optimalgraphedit}

Input:
\begin{itemize}
\item $G$, a ``small'' graph, one subgraph from the output of the graph splitting.
\item $\mathcal{D}$, the graph database
\end{itemize} 

Output:
\begin{itemize}
\item $G'$, the graph which is the result of performing the optimal edit operation upon $G$
\end{itemize} 

\begin{algorithmic}
%\IF {$i\geq maxval$} 
\FOR{$  x \in \mathcal{D} $}
\IF{$G \subseteq x $} 

\FOR{$ G' \in B(G,1) \wedge G' \subseteq x $}
\STATE \COMMENT {Every $G'$ corresponds to some valid edit operation upon $G$ (that is, both $G$ and $G'$ are contained in this specific graph $x$).}
\STATE $\phi(x, G) \gets \phi(x, G) + 1$ 
\ENDFOR

\ENDIF
\ENDFOR


\RETURN $\underset{x \in B(G, 1)}{\operatorname{arg\,max}}  \phi(x, G)$

\end{algorithmic}
\end{algorithm}
%-----------------------------------------------

%One of the limitations of this approach is that edge additions between vertices in different ``subclusters'' is not considered. This becomes a larger factor as the partial graph approach the size of
%the full graph $G$.

%If we can find a specific frequent subgraph in the partial graph, then we can try to infer what the next most likely graph should be for that part of the complete partial graph. 

%However, it is not possible to just try to match the complete observed partial graph with a frequent subgraph, since once the partial graph is large enough, there won't be any \emph{one} frequent subgraph which can be matched to it. 
%Rather it will consists of several frequent subgraphs connected to each other.

%The idea behind the algorithm is the following. We will try to find frequent subgraphs, as big as possible in the partial such graph, such that the union of these frequent subgraph is the partial graph itself. 
%Since the partial graph and each frequent subgraph is connected, we also impose the condition upon the chosen frequent subgraphs that they are overlapping. We demand that the union of any chosen partition must be connected.
%This is solved in the algorithm by always selecting a new frequent subgraph that shares some common vertex with one of the already chosen frequent subgraphs, thus always maintaining this property.
